package ThirdWeek;

public class Friday {
    //704、朴素二分查找
    public int search(int[] nums, int target) {
        int left = 0,right = nums.length - 1;
        while(left <=right) {
            //int mid = (right + left) / 2;//这样求中间值的时候，可能会存在溢出
            int mid = left + (right - left) / 2;//这样就防止溢出了
            if(target == nums[mid]) {
                return mid;
            }else if(target > nums[mid]) {
                left = mid + 1;
            }else {
                right = mid - 1;
            }
        }
        return -1;
    }

    //67、二进制求和
    public String addBinary(String a, String b) {
        StringBuilder ret = new StringBuilder();

        int carry = 0;
        int sum = 0;
        //从后往前进行相加，之后放进ret中，最后在对ret进行翻转
        for (int i = a.length() - 1,j = b.length() - 1;i >= 0 || j >= 0;i--,j--) {
            sum = carry;
            int a1 = i >= 0 ? a.charAt(i) - '0' : 0;
            int b1 = j >= 0 ? b.charAt(j) - '0' : 0;
            sum = a1 + b1 +carry;
            ret.append(sum % 2);
            carry = sum / 2;
        }
        ret.append(carry == 1 ? carry : "");

        return ret.reverse().toString();
    }
}
